package com.itheima.mianshi.quick;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] a = {1, 3, 2, 5, 4, 6, 7, 8, 9, 10};
        quick(a, 0, a.length - 1);
    }

    /**
     * 快速排序
     *
     * @param a
     * @param l
     * @param h
     */
    public static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h); // p是分区点
        quick(a, l, p - 1); // 递归左边
        quick(a, p + 1, h); // 递归右边
    }

    /**
     * 单边循坏快排
     *
     * @param a
     * @param l
     * @param h
     * @return 返回分区点
     */
    public static int partition(int[] a, int l, int h) {
        int pivot = a[h]; // 以最后一个元素为基准
        int i = l;
        for (int j = l; j < h; j++) {
            if (a[j] < pivot) {
                if (i != j) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
                i++;
            }
        }
        if (i != h) {
            int temp = a[i];
            a[i] = a[h];
            a[h] = temp;
        }
        System.out.println("第" + (i + 1) + "轮排序后的数组" + java.util.Arrays.toString(a));
        return i;
    }

    /**
     * 双边循环快排
     *
     * @param a
     * @param l
     * @param h
     * @return 返回分区点
     */
    public static int partition2(int[] a, int l, int h) {
        int pivot = a[l]; // 以第一个元素为基准
        int i = l;
        int j = h;
        while (i < j) {
            while (i < j && a[j] >= pivot) {
                j--;
            }
            while (i < j && a[i] <= pivot) {
                i++;
            }
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[l] = a[i];
        a[i] = pivot;
        System.out.println("第" + (i + 1) + "轮排序后的数组" + java.util.Arrays.toString(a));
        return i;
    }
}
